package com.foxzzz.back.tracking;

import java.util.ArrayList;
import java.util.List;

public class Solution22 {
    public List<String> generateParenthesis(int n) {
        List<String> list=new ArrayList<>();
        char[] sb=new char[2*n];
        gen(list,sb,n,n);
        return list;
    }
    /*            0,0
           /   \     \     \
        1,1     2,1  2,2   3,3
        /  \     |    |
       1,1 2,2  1,2  1,1
        /
      1,1
     */

    public void gen(List<String> list,char[] sb,int left,int right){
        if(left==0&&right==0) {
            list.add(new String(sb));
            return;
        }
        for(int i=1;i<=left;i++)
            for(int j=1;right-j>=left-i;j++) {
                for(int k=0;k<i;k++){
                   sb[sb.length-left-right+k]='(';
              }
              for(int k=0;k<j;k++){
                    sb[sb.length-left-right+i+k]=')';
               }
              gen(list,sb,left-i,right-j);
            }
    }

    public static void main(String[] args) {
        System.out.println(new Solution22().generateParenthesis(3));
    }
}
